#include <iostream>
#include <vector>

using namespace std;

void shell_sort(vector<int> &vec)
{
    int len = vec.size();
    for(int gap = len/2; gap > 0; gap /= 2)
    { 
        // 对每一躺进行插入排序
        for(int i = gap; i < len; ++i) //对于每趟的第一个元素是有序的，从第二个元素开始，所以是i = gap 
        {
            int tempNum = vec[i]; //将第二个数存到tempNum中，如果第一个数大于第一个数，便于将第一个数后移到第二个数的位置
            int j;
            //对一趟中的数组进行排序，注意数字之间的间隔是gap
            for(j = i - gap; j >= 0 && vec[j] > tempNum; j -= gap) //如果第一个数大于第二个数,则将第一个数后移到第二个数的位置。j = j - gap，对这趟的数从后往前扫描
            {
                vec[j + gap] = vec[j];
            }
            vec[j + gap] = tempNum;//上面的循环已经执行了j = j - gap不满足条件，所以是将tempNum放到j + gap的位置
        }
    }
}

int main()
{
    int num;
    cin >> num;

    vector<int> vec;
    int temp;
    for(int i = 0; i < num; ++i)
    {
        cin >> temp;
        vec.push_back(temp);
    }

    shell_sort(vec);

    for(vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
    {   
        cout << *it << " ";    
    }
    cout << endl;

    return 0;
}
